package com.zl.learning.arithmetic.my;

import com.zl.learning.arithmetic.util.SortUtil;

import static com.zl.learning.arithmetic.util.SortUtil.printArray;

/**
 * Created by sunqianqian on 2015/3/18.
 * <p>
 * 快速排序由 C. A. R. Hoare 在1962年提出。它的基本思想是：通过一趟排序将要排序的数据
 * 分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此
 * 方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成
 * 有序序列。
 */
public class QuickSort {

    /**
     * 经典排序算法 - 快速排序Quick sort
     * 1．先从数列中取出一个数作为基准数。
     * 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
     * 3．再对左右区间重复第二步，直到各区间只有一个数。
     */
    private static void quickSort(int[] a, int low, int high) {
        if (low < high) {
            int i = low, j = high, x = a[low];
            while (i < j) {
                while (i < j && a[j] > x) {
                    j--;
                }
                if (i < j) {
                    a[i] = a[j];
                    i++;
                }
                while (i < j && a[i] < x) {
                    i++;
                }
                if (i < j) {
                    a[j] = a[i];
                    j--;
                }
            }
            a[i] = x;
            quickSort(a, low, i - 1);
            quickSort(a, i + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] a = SortUtil.getRandomArray(10);
        printArray(a);
        quickSort(a, 0, a.length - 1);
        printArray(a);
    }
}
